This invention relates to an arrangement for finding names in a directory in spite of spelling and typing errors.
Computer programs that look up names in a directory often require the provided name to be spelled correctly. In systems that tolerate errors, two basic techniques are used.
Some systems return all the names that are phonetically similar to the name requested by the user and force the user to search through a potentially bewildering array of possibilities. A user requesting a name like "bovie", for example, might be confronted with a list that includes names like "baffa", "bavier", "boffa", "boivie", "bova", "bove", "bovee", "bovey" and "bovie". This scheme puts much of the burden on the user who then must manually search a long list of possibilities to find the desired entry. This scheme also has another problem. If a user makes a nonphonetic error such as requesting "bowie" when the desired name is actually "boivie", the desired name would not even appear in the list of possibilities.
The second technique "corrects" errors by finding entires in the directory that are "close" to the name provided by the user. A directory entry is close to the requested name if it can be transformed into that name by a small number of insertions, deletions, substitutions and transpositions. The most common means of finding close names involves making small changes to the desired name and looking up the names that result from those small changes. This can take a great deal of computing time.
Because of the computation time required, practical implementations of the second technique put a bound on the number of errors that can be tolerated in a given word. Usually the bound is 1. Thus a user requesting "bove" would not be able to find a desired entry if the correct spelling of the name were "boivie".